// Package binaryFind /*
/*

方法1：
时间复杂度：O(logN)
空间复杂度：O(1)

case1:

r:

*/
package binaryFind

func search(nums []int, target int) int {
	if nums == nil || len(nums) == 0 {
		return -1
	}
	i, j := 0, len(nums)-1
	// 存在没有等于target的元素的情况，所以用i<=j查询无定值情况
	for i <= j {
		mid := (i + j) / 2
		if target == nums[mid] {
			return mid
		}
		// 表示旋转的前半部分序列包含在[0...mid)中
		// 否则表示旋转的后半部分序列包含在(mid, len(nums)-1]中
		if nums[mid] >= nums[0] {
			// 说明target在[0...mid)区间内
			// 否则在(mid.....len(nums)-1]区间内
			if target >= nums[0] && target < nums[mid] {
				j = mid - 1
			} else {
				i = mid + 1
			}
		} else {
			// [mid... len(nums)-1]包含于旋转的后半部分序列中
			if target > nums[mid] && target <= nums[len(nums)-1] {
				i = mid + 1
			} else {
				j = mid - 1
			}
		}
	}
	return -1
}

// 二分查找
func binarySearch(nums []int, target, i, j int) int {
	if nums == nil || len(nums) == 0 {
		return -1
	}
	for i <= j {
		mid := (i + j) / 2
		if nums[mid] == target {
			return mid
		} else if nums[mid] > target {
			j = mid - 1
		} else {
			i = mid + 1
		}
	}
	return -1
}
